package com.ward.tree;

import java.util.Stack;

/**
 * Created by ward on 2017-09-21.
 */
public class BinaryTree {
    public class Node {

        private Integer value;

        private Integer index;//树中 节点的下标 从1开始 而非0
        private Node leftNode;
        private Node rightNode;
        private Node parentNode;


        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        public Node getParentNode() {
            return parentNode;
        }

        public void setParentNode(Node parentNode) {
            this.parentNode = parentNode;
        }

        public Integer getIndex() {
            return index;
        }

        public void setIndex(Integer index) {
            this.index = index;
        }

        public Node(Integer value, Integer index, Node leftNode, Node rightNode, Node parentNode) {
            super();
            this.value = value;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.parentNode = parentNode;
            this.index = index;
        }
    }

    private Node rootNode;

    public Node getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node rootNode) {
        this.rootNode = rootNode;
    }


    private Node getNodeFromArray(Integer[] originData, Integer arrayIndex) {
        Integer nodeIdex = arrayIndex + 1;
        Node node = new Node(originData[arrayIndex], nodeIdex, null, null, null);
        return node;
    }




    /**
     * @desc  把数组转换成一棵完全二叉树，注意 二叉树节点的下标index 之间的关系 如下图
     *
     *                    1
     *                  /  \
     *                 ......
     *             /            \
     *           n-1             n
     *          /   \          /   \
     *    2*(n-1) 2*(n-1)-1  2*n  2*n+1
     * @param originData
     */
    public void convertArrayToCompleteBinaryTree(Integer[] originData) {
        //注意 数组的下标 是从0开始的，要考虑此处 与 二叉树树节点下标的区别
        if (originData.length < 0) {
            return;
        }
        Node node = this.getNodeFromArray(originData, 0);
        this.setRootNode(node);
        Node tempNode = node;
        Stack<Node> nodeStack = new Stack<>();
        //nodeStack.push(node);
        while (null != tempNode || !nodeStack.isEmpty()) {
            Integer breakFlag=0;
            //优先把左孩子创建,同时入栈
            while (tempNode.getIndex() * 2 <= originData.length && null == tempNode.getLeftNode()) {
                Node intNode = getNodeFromArray(originData, tempNode.getIndex() * 2 - 1);
                tempNode.setLeftNode(intNode);
                intNode.setParentNode(tempNode);
                nodeStack.push(tempNode);
                tempNode = intNode;
                breakFlag++;
            }
            if (!nodeStack.isEmpty()) {
                tempNode = nodeStack.pop();
                if (tempNode.getIndex() * 2 + 1 <= originData.length) {
                    Node intNode = getNodeFromArray(originData, tempNode.getIndex() * 2 + 1 - 1);
                    tempNode.setRightNode(intNode);
                    intNode.setParentNode(tempNode);
                    tempNode = intNode;
                }
                breakFlag++;
            }
            if(0==breakFlag){
                break;
            }
        }
        return;
    }

    /**
     * @param subRoot
     * @desc 递归遍历二叉树
     */

    public void inorderTraversalRecursive(Node subRoot) {
        if (null != subRoot.getLeftNode()) {
            inorderTraversalRecursive(subRoot.getLeftNode());
        }
        System.out.print(subRoot.getValue() + ",");
        if (null != subRoot.getRightNode()) {
            inorderTraversalRecursive(subRoot.getRightNode());
        }
        return;
    }


    public static void main(String[] args) {
        Integer[] originData = {1, 2, 3, 4, 5, 6, 7, 8,9,10,11,12,13};
        BinaryTree tree = new BinaryTree();
        tree.convertArrayToCompleteBinaryTree(originData);
        tree.inorderTraversalRecursive(tree.getRootNode());
    }
}
